package Chapter2;

/**素数线性表
 * 概念：素数 是指除1和自身外，不能被其他数整除的自然数
 * 算法描述：
 * 1.显然最小素数是2，不需要测试其他偶数
 * 2.测试奇数，需要使用3~根号key的每一个素数prime进行测试，若存在一个素数prime，有key%prime==0，则key不是素数
 * 3.只有测试完指定范围中的所有素数，才能确定key是素数
 */
public class PrimeList {
    private int range;                          //素数范围上限
    private SinglyList<Integer> list;

    public PrimeList(int range){
        if (range<=1)
            throw new java.lang.IllegalArgumentException("range="+range);
        this.range=range;
        this.list=new SinglyList<Integer>();
        this.list.insert(2);
        Node<Integer> rear=this.list.head.next;
        for (int key=3;key<=range;key+=2){
            if (this.isPrime(key)){
                rear.next=new Node<Integer>(key,null);
                rear=rear.next;
            }
        }
    }

    public boolean isPrime(int key){
        if (key<=1)
            throw new java.lang.IllegalArgumentException("key="+key);
        int sqrt=(int) Math.sqrt(key);
        for (Node<Integer> p=this.list.head.next;p!=null&&p.data<=sqrt;p=p.next)
            if (key%p.data==0)
                return false;
        return true;
    }

    public String toString(){
        return "2~"+range+"素数集合："+list.toString()+","+list.size()+"个元素";
    }

    public static void main(String[] args) {
        System.out.println(new PrimeList(100).toString());
    }
}
